1073E - Segment Sum - CodeForces Solution

/* Yukimi */	
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

typedef long long LL;
typedef long long ll;
typedef complex<double> comp;
typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<char, int> PCI;
typedef pair<double,double> PDD;
typedef unsigned long long ull;
typedef long long ll;

const comp I(0,1);
const double pi = acos(-1.0);
// const int Inf = 1e18;
const int mod = 998244353;
const int N = 2e5 + 10;
const int M = N * 2;
const double eps = 1e-6;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
PII f[30][1030];
int n, k;
int a[20];
int P[20];
int len = 0;
PII dfs(int pos, bool limit, int sta, bool lead)
{
    if(!pos) {
        if(__builtin_popcount(sta) <= k) return {1, 0};
        return {0, 0};
    }
    if(!limit && !lead && f[pos][sta].second != -1) //没限制并且dp值已搜索过
        return f[pos][sta];
    int up = limit ? a[pos] : 9;
    LL res = 0;
    PII ans = {0, 0};
    for (int i = 0; i <= up; i++) {
        int nsta;
        if(lead && i == 0) nsta = sta;
        else nsta = sta | (1 << i);
        PII now = dfs(pos - 1, limit && i == up, nsta, lead && i == 0);
        ans.first = (ans.first + now.first) % mod;
        ans.second = (ans.second + now.first * P[pos - 1] % mod * i % mod) % mod;
        ans.second = (ans.second + now.second) % mod; 
    }
    if(!limit && !lead) //记搜，可复用
        f[pos][sta] = ans;
    return ans;
}
int DP(int x) {
    len = 0;
    while(x) {
        a[++len] = x % 10;
        x /= 10;
    }
    for (int i = 0; i < 20; i++) for (int j = 0; j < 1029; j++) f[i][j].first = f[i][j].second = -1;
    return dfs(len, 1, 0, 1).second;
}
void solve() {
    P[0] = 1;
    for (int i = 1; i <= 18; i++) P[i] = (P[i - 1] * 10) % mod;
    int l, r;
    cin >> l >> r >> k;
    cout << (DP(r) - DP(l - 1) + mod) % mod;
}

   
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0; 
}